§ 1.1 Field of the Invention
The present invention concerns the communication of data over networks, such as the Internet for example. More specifically, the present invention concerns scheduling the servicing (e.g., dispatching) of cells or packets buffered at input ports of a switch.
§ 1.2 Related Art
Switches and routers are used in networks, such as the Internet for example, to forward data towards its destination. The need for large-scale switches and routers is introduced in § 1.2.1 below. Then, two types of switches, as well as disadvantages and challenges in each of these two types of switches, are introduced in § 1.2.2 below.
§ 1.2.1 The Need for Large-scale (e.g., Terabit) Routers and Switches
Many expect that Internet traffic will continue to grow explosively. Given this assumption, high-speed switches and routers (e.g., those having a throughput over one Terabit per second) will become necessary. Most high-speed packet switches adopt a fixed-size cell in the switch fabric. If variable length packets are to be supported in the network, such packets may be segmented and/or padded into fixed-sized cells upon arrival, switched through the fabric of the switch, and reassembled into packets before departure. There are two main types of high-speed switches, each introduced in § 1.2.2 below.
§ 1.2.2 Types of Switches (Single Stage Versus Multi-stage) and Their Characteristics
There are two main types of high-speed switches—namely single stage and multi-stage. Single stage switches and perceived limits of single stage switches are introduced in §§ 1.2.2.1 and 1.2.2.2, respectively, below. Similarly, multi-stage switches and perceived limits of multi-stage switches are introduced in §§ 1.2.2.3 and 1.2.2.4, respectively, below.
§ 1.2.2.1 Single Stage Switch Architectures
A so-called “crossbar” switch is a classic example of a single stage switch. In a crossbar switch, identical switching elements are arranged on a matrix plane. The article, N. McKeown, M. Izzard, A. Mekkiltikul, W. Ellerisick and M. Horowitz, “Tiny-Tera: A Packet Switch Core,” IEEE Micro., pp. 26–33, (January–February 1997) (incorporated herein by reference and hereafter referred to as “the Tiny-Tera article”) proposes a 320 gigabit per second crossbar switch fabric that uses a centralized scheduler referred to as “iSLIP”. The article H. J. Chao and J-S Park, “Centralized Contention Resolution Schemes for a Large-Capacity Optical ATM Switch,” Proc. IEEE ATM Workshop '97 (Fairfax, Va., May. 1998) (incorporated herein by reference and hereafter referred to as “the Chao article”) introduced a centralized contention resolution scheme for a large capacity crossbar optical switch. The article E. Oki, N. Yamanaka, Y. Ohtomo, K. Okazaki and R. Kawano, “A 10-Gb/s (1.25 Gb/s×8) 4×2 0.25 μm CMOS/SIMOX ATM Switch Based on Scalable Distributed Arbitration,” IEEE J. of Solid-State Circuits, Vol. 34, No. 12, pp. 1921–1934 (Dec. 1999) (incorporated herein by reference and hereafter referred to as “the Oki article”) describes a high-speed switch chip having a throughput of 40 Gb/s, for a high-speed crosspoint-buffered crossbar switching system.
§ 1.2.2.2 Limits of Single Stage Switch Architectures
The switching techniques used in single stage switches, such as those described in the articles referenced in § 1.2.2.1, are effective up to a certain switch size. Unfortunately, however, with such techniques, the complexity of the switching elements is proportional to the square of the number of switch ports. As a practical matter, this limits the feasibility of using such techniques in a large scale (e.g., Terabit per second and above) switch.
§ 1.2.2.3 Multi-Stage Switch Architectures
In view of the limits of single stage switches, multiple-stage switch architectures have been introduced. For example, the so called “Clos-network” switch has three stages and is very attractive because of its scalability. See the article, C. Clos, “A Study of Non-Blocking Switching Networks,” Bell Sys. Tech. Jour., pp. 406–424 (March 1953) (incorporated herein by reference and hereafter referred to as “the Clos article”). More specifically, the three stages include (i) input modules, (ii) a central switching fabric (incorporated in central modules), and (iii) output modules.
Clos-network switches have been categorized into two types—those with buffers to store cells in the second-stage (central) modules and those with no buffers in the second-stage (central) modules. For example, the article, T. Chaney, J. A. Fingerhut, M. Flucke, J. S. Turner, “Design of a Gigabit ATM Switch,” Proc. IEEE INFOCOM 97, pp. 2–11 (April 1997) (incorporated herein by reference and hereafter referred to as “the Chaney article”) discusses a gigabit ATM switch using buffers in the second-stage modules. In the switch architecture discussed in the Chaney article (hereafter referred to as “the Chaney switch”), every incoming cell is randomly distributed from the first-stage to the second-stage module to balance the traffic load in the second-stage. This is commonly referred to as “random dispatching”. The buffers in the second-stage modules are used to resolve contention among cells from different first-stage modules. See the article J. Turner and N. Yamanaka, “Architectural Choices in Large Scale ATM Switches,” IEICE Trans. Commun., Vol. E81-B, No. 2, pp. 120–137 (February 1998) (incorporated herein by reference and hereafter referred to as “the Turner article”).
An example of a switch architecture with no buffers in the second-stage modules is provided in the article F. M. Chiussi, J. G. Kneuer, and V. P. Kumar, “Low-Cost Scalable Switching Solutions for Broadband Networking: The ATLANTA Architecture and Chipset,” IEEE Commun. Mag., pp. 44–53 (December 1997) (incorporated herein by reference and hereafter referred to as “the Chiussi article”). Since there are no buffers in the second-stage modules to resolve potential contention, how cells are dispatched from the first-stage to the second-stage becomes important. The simple random distribution used in the Chaney switch may be used in the switch discussed in the Chiussi article (hereafter referred to as “the Chiussi switch”) under certain conditions. Given the potential for contention, some buffers are provided in the first and third stages of the Chiussi switch. Although there are some studies of routing algorithms where every stage has no buffers, such algorithms require a contention resolution function for output ports, before cells even enter the multiple-stage switches. See, e.g., the articles, C. Y. Lee and A. Y. Qruc, “A Fast Parallel Algorithm for Routing Unicast Assignments in Benes Networks,” IEEE Trans. on Parallel and Distributed Sys., Vol. 6, No. 3, pp. 329–333 (March 1995), and T. T. Lee and S-Y Liew, “Parallel Routing Algorithms in Benes-Clos Networks,” Proc. IEEE INFOCOM '96, pp. 279–286 (1996). (Both of these articles are incorporated herein by reference.) Such a pre-switch contention resolution function is challenging to implement in high-speed switches.
§ 1.2.2.4 Problems with Known Multiple-stage Switch Architectures
To provide high performance (e.g., high throughput), known multiple-stage switch architectures will typically require speed-up of the internal switching fabric (i.e., in the second-stage modules) and/or resequencing. For example, the Chaney switch provides high performance if the internal speed-up factor is set to be more than 1.25. As is known, speed-up of the switching fabric can be accomplished by increasing the number of central modules and/or increasing the internal link speed used in the central modules. Unfortunately, however, in the Chaney switch, buffers used in the second-stage modules cause cells to become out-of-sequence. Since the Chiussi switch does not use buffers in its second-stage modules, cell out-of-sequence problems are not encountered. Assuming that a random dispatching scheme is used to forward cells from the first stage to the second stage of the Chiussi switch, to minimize the chance of contention at the second stage, the internal speed-up factor has to be increased further. For example, to achieve 100% throughput using random dispatching in a large-size Chiussi switch, the speed-up is set to about 1.6 as indicated in the Chiussi article.
As should be appreciated from the foregoing, to be used in today's more demanding environments, the Chaney switch requires cell resequencing, which is challenging, and at least moderate speed-up, which increases costs. To be used in today's more demanding environments, the Chiussi switch requires even more speedup, which increases costs even more. In view of these problems with known switch architectures, a scalable switch architecture having a high throughput, avoiding out-of-sequence cells (e.g., by eliminating buffers in the second stage), and avoiding speed-up of the switch fabric is coveted.